<?php
/**
 * @title 47. 全排列 II - 递归
 * @author start2004
 */


class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique($nums) {
        // /**
        //  * @since 2020-09-18 数组长度
        //  */
        // $len = count($nums);
        // if($len == 0){
        //     return [];
        // } else {}

        /**
         * @since 2020-09-18 排序
         */
        sort($nums);

        /**
         * @since 2020-09-18 全排列
         */
        $result = self::find($nums);

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 返回全排列
     * @author start2004
     * @since 2020-09-18 Created
     *
     * @param array $nums
     * @return array
     */
    public function find($nums = []){
        /**
         * @since 2020-09-18 结果集
         */
        $result = [];

        /**
         * @since 2020-09-18 数量
         */
        $len = count($nums);
        if($len >= 3){
            /**
             * @since 2020-09-18 依次做第1个元素
             */
            $prev = null;
            foreach ($nums as $key=>$num){
                if($num === $prev){
                    continue;
                } else {
                    /**
                     * @since 2020-09-18 记录上次元素, 防止重复
                     */
                    $prev = $num;

                    /**
                     * @since 2020-09-18 递归结果
                     */
                    $tmp = $nums;
                    unset($tmp[$key]);
                    $datas = self::find($tmp);

                    /**
                     * @since 2020-09-18 增加元素num
                     */
                    foreach ($datas as $data){
                        $data[] = $num;
                        $result[] = $data;
                    }

                    /**
                     * @since 2020-09-18 还原
                     */
                    // $nums[$key] = $num;
                }
            }
        } elseif($len == 2) {
            $num1 = current($nums);
            $num2 = next($nums);

            if($num1 == $num2) {
                $result[] = $nums;
            } else {
                $result = [
                    [$num1, $num2],
                    [$num2, $num1],
                ];
            }
        } elseif($len == 1){
            $result[] = $nums;
        } else {
            /**
             * @since 2020-09-18 len = 0, 返回空数组
             */
        }

        /**
         * @return
         */
        return $result;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.21_11.php
 */
$datas = [
    // [1,1,2],
    // [3,0,3],
    [2,2,1,1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->permuteUnique($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
